'''
https://leetcode.cn/problems/minimum-window-substring/description/
'''


class Solution:
    def minWindow(self, s: str, t: str) -> str:
        times = [0] * 128
        debt = len(t)
        for c in t:
            times[ord(c)] -= 1
        l, r, n = 0, 0, len(s)
        min_len, start = float('inf'), -1
        while r < n:
            times[ord(s[r])] += 1
            if times[ord(s[r])] <= 0:
                # 一次有效的覆盖
                debt -= 1
            while l <= r and debt == 0:
                # l 尽可能的往右扩，循环里时一定正确的扩，出了循环是错误的外置
                if r - l + 1 < min_len:
                    min_len = r - l + 1
                    start = l
                times[ord(s[l])] -= 1
                if times[ord(s[l])] < 0:
                    debt += 1
                l += 1
            r += 1
        return s[start:start + min_len] if start != -1 else ""
